
# -*- coding: utf-8 -*-
'''
projecto- classe destinada ao algoritmo de ordenação: quicksort
autor- Ana Isabel Marques 6052
data de criação do módulo- 31/05/2013

Complexidade Computacional:
        pior caso - O(n²)
        caso médio - O(n log(n))
        melhor caso - O(n log(n)) 
'''

class Quicksort:
        '''
        Constructor
        @param A - lista de números inteiros
        '''
        def __init__(self, A):
                self.A = A
                pass

        '''
        Este método divide a lista A em duas sublistas.
        @param p
        @param r
        '''
        def partition(self, p, r):
                
                x = self.A[r]
                i = p - 1
	
                for j in range (p, r):
                        if self.A[j] <= x:
                                i = i + 1
                                self.A[i], self.A[j] = self.A[j], self.A[i]
                                pass
                        pass
   
                self.A[i+1], self.A[r] = self.A[r], self.A[i+1]
                
                return i + 1

        '''
        Ordena uma lista com o método quicksort
        Retorna uma lista ordenada
        @param p
        @param r
        '''
        def quicksort(self, p, r):
                if p < r:
                        q = self.partition(p, r)
                        self.quicksort(p, q - 1)
                        self.quicksort(q + 1, r)
                        pass
                return self.A
        
        pass
pass
